K: Rozdeľovanie sociálneho grafu
50 bodov	Časový limit: 1000 ms

Keďže autorom zadaní ZENITu bolo vyčítané, že píšu dlhé texty, rozhodli sme sa príbeh vedúci k tejto úlohe vypustiť. Takže o divokých konfliktoch, chlpatých opiciach, predaji zubných kefiek rôznych farieb a samozrejme Lukášovi sa dočítate možno nabudúce.

Kto sa dočítal až sem, zrejme pozná pojem grafu (je to to isté, čo v úlohe o párty). Graf pozostáva z vrcholov a hrán. V našom prípade sa budeme baviť o neorientovanom ohodnotenom grafe, pričom hodnoty hrán budú nezáporné čísla.

Chceme ofarbiť vrcholy grafu dvoma farbami: čiernou a červenou. Skóre ofarbenia je súčet hodnôt hrán, ktoré vedú medzi vrcholmi rôznych farieb. Prečítajte zo vstupu graf a vypíšte najvyššie možné dosiahnuteľné skóre na tomto grafe.

Na prvom riadku vstupu je počet vrcholov N (1 ≤ N ≤ 24) a počet hrán M (0 ≤ M ≤ 50,000). Na ďalších M riadkoch sú trojice čísel: popisy hrán. Prvé dve čísla sú vrcholy (v rozmedzí 1 a N), posledné číslo je ohodnotenie hrany (celé, nezáporné, nepresahujúce 1,000,000). Môžete predpokladať, že každé dva vrcholy sú spojené najviac jednou hranou a že každá hrana spája dva rôzne vrcholy.

Poznámka: pre polovicu vstupov bude platiť N ≤ 20. Za túto úlohu je relatívne ľahké získať približne polovicu bodov, ale relatívne ťažké získať všetky. Na testovači máte okrem nasledovných príkladov ešte jeden, kde N = 24.

> Príklady:

vstup

3 2 1 2 7 1 3 4

výstup

11

vstup

4 5 1 2 7 4 2 6 3 1 9 4 1 5 3 4 9

výstup

31

vstup

6 9 1 2 15 1 3 3 2 3 1 2 4 4 4 3 3 3 6 2 6 5 7 5 3 7 4 5 7

výstup

41

Jedným z optimálnych riešení je ofarbiť vrcholy číslo 2 a 5 na červeno a zvyšné vrcholy na čierno. Hrany, spájajúce vrcholy rôznych farieb, sú (1,2),(2,3),(2,4),(3,5),(4,5) a (5,6). Skóre je teda 15+1+4+7+7+7 = 41. Inou možnosťou na dosiahnutie optimálneho skóre je zafarbiť na červeno vrcholy 1,4 a 6 (a zvyšné na čierno).

---